package com.algorithm.ch1.lzr.linkedlist;

/**
 * 合并两个有序链表
 * 将两个有序链表合并为一个新的有序链表并返回 新链表是通过拼接给定的两个链表的所有节点组成的
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 * @author lzr
 * @date 2018/8/18
 */
public class MergeTwoLists {

    public static void main(String[] args) {
        ListNode listNodeA1 = new ListNode(1);
        ListNode listNodeA2 = new ListNode(2);
        ListNode listNodeA3 = new ListNode(4);
        ListNode listNodeB1 = new ListNode(1);
        ListNode listNodeB2 = new ListNode(3);
        ListNode listNodeB3 = new ListNode(4);
        listNodeA1.next = listNodeA2;
        listNodeA2.next = listNodeA3;
        listNodeA3.next = null;
        listNodeB1.next = listNodeB2;
        listNodeB2.next = listNodeB3;
        listNodeB3.next = null;
        ListNode listNode = mergeTwoLists(listNodeA1, listNodeB1);
        System.out.print(listNode.val);
    }

    /**
     * 有序：需要循环遍历链表数据并比较大小
     *
     * @param linkA
     * @param linkB
     * @return
     */
    public static ListNode mergeTwoLists(ListNode linkA, ListNode linkB) {
        if (linkA == null) {
            return linkB;
        }
        if (linkB == null) {
            return linkA;
        }
        //合并后的头指针
        ListNode head;
        //用于扫描链表
        ListNode pA = linkA;
        ListNode pB = linkB;
        if (linkA.val < linkB.val) {
            head = linkA;
            pA = linkA.next;
        } else {
            head = linkB;
            pB = linkB.next;
        }
        ListNode p = head;
        while (pA != null && pB != null) {
            if (pA.val < pB.val) {
                p.next = pA;
                pA = pA.next;
            } else {
                p.next = pB;
                pB = pB.next;
            }
            p = p.next;
        }
        if (pA != null) {
            p.next = pA;
        } else if (pB != null) {
            p.next = pB;
        }
        return head;
    }



}
